package com.maltys.monotonic.stack;

import org.springframework.util.CollectionUtils;

import java.util.*;

/**
 * @author maltys
 * @link <a href="https://leetcode.cn/problems/next-greater-element-ii/">下一个更大的数II</a>
 */
public class NextGreaterElementII {
    public static void main(String[] args) {
        NextGreaterElementII elementI = new NextGreaterElementII();
        int[] ints = elementI.nextGreaterElement(new int[]{1, 3, 4, 2});
        System.out.println(Arrays.toString(ints));
    }

    public int[] nextGreaterElement(int[] nums) {
        List<Integer> list = new ArrayList<>();
        for (int num : nums) {
            list.add(num);
        }
        for (int num : nums) {
            list.add(num);
        }
        Stack<Integer> stack = new Stack<>();
        int[] result = new int[nums.length];
        Arrays.fill(result, -1);
        for (int i = 0; i < list.size(); i++) {
            while (!stack.isEmpty() && list.get(i) > list.get(stack.peek())) {
                Integer idx = stack.pop();
                if (idx < nums.length) {
                    result[idx] = list.get(i);
                }
            }
            stack.push(i);
        }
        return result;
    }
}
